package com.aqie.hard.binaryTree;

import com.aqie.easy.structure.TreeNode;

/**
 * 124 二叉树最大路径和 todo
 * 路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点
 */
public class MaxPathSum {
    /**
     * 3ms
     * @param root
     * @return
     */
    public int maxPathSum(TreeNode root){
        int[] result = new int[1];
        result[0] = Integer.MIN_VALUE;
        max(root,result);
        return result[0];
    }
    private int max(TreeNode root,int[] result){
        if(root == null){
            return 0;
        }
        int left = Math.max(0,max(root.left,result)); //负数置0，说明不走这个分支
        int right = Math.max(0,max(root.right,result));
        int res = Math.max(left,right) + root.val;  //res是左右子树其中一条经过root节点的最大路径和
        result[0] = Math.max(result[0],left + right + root.val); //result是以每个节点作为根节点时最大的路径和，也就是左子树最大路径和加上右子树最大路径和加上自身，子树路径和为负数则取0，表示不走子树
        return res;
    }

    /**
     * 2, O(N) O(logN) 4ms
     */
    int max_sum = Integer.MIN_VALUE;

    public int max_gain(TreeNode node) {
        if (node == null) return 0;

        // max sum on the left and right sub-trees of node
        int left_gain = Math.max(max_gain(node.left), 0);
        int right_gain = Math.max(max_gain(node.right), 0);

        // the price to start a new path where `node` is a highest node
        int price_newpath = node.val + left_gain + right_gain;

        // update max_sum if it's better to start a new path
        max_sum = Math.max(max_sum, price_newpath);

        // for recursion :
        // return the max gain if continue the same path
        return node.val + Math.max(left_gain, right_gain);
    }

    public int maxPathSum2(TreeNode root) {
        max_gain(root);
        return max_sum;
    }

}
